import java.awt.*;
import java.util.Stack;

public class StackPractice {
    class ListNode {
        int value;
        ListNode next;
        public ListNode(int value) {
            this.value = value;
        }
    }
    //打印链表
    public void print(ListNode head) {
        while (head != null) {
            System.out.print(head.value+" ");
            head = head.next;
        }
    }
    //创建一个链表，用于测试
    public void createList() {
        ListNode cur = new ListNode(1);
        ListNode head = cur;
        for (int i = 2; i < 5; i++) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        System.out.print("原来的链表：");
        print(head);
        System.out.println();
        //递归的方法逆序打印链表
        System.out.print("递归逆序：");
        reversePrintList(head);
        System.out.println();
        //利用栈方法逆序打印链表
        System.out.print("用栈逆序：");
        stackReversePrintList(head);
        System.out.println();
    }
    //逆序打印单链表(递归)
    public void reversePrintList(ListNode head) {
        //如果只有一个头节点，直接输出
        if(head.next == null) {
            System.out.print(head.value+" ");
            return;
        }
        reversePrintList(head.next);
        System.out.print(head.value+" ");
    }
    //逆序打印链表（栈实现）
    //利用栈的特性，先进后出
    public void stackReversePrintList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        //节点不为空，直接放入栈中，并且链表节点向后移动
        while(head != null) {
            stack.push(head);
            head = head.next;
        }
        //开始出栈
        //当栈不为空
        while(!stack.isEmpty()) {
            //节点出栈，拿到结点的值
            System.out.print(stack.pop().value+" ");
        }
    }

}
